Raytracing is a field of computer graphics that can produce superior, photorealistic digital images. Raytracing or ray-casting is a three-dimensional (3-D) rendering technique that determines the location of an object in 3-D and calculates shadows, reflections, and hidden surfaces based on lighting conditions and locations, as well as material characteristics. The visibility of surfaces is determined by tracing rays of light from the viewer's vantage to objects in a scene.
Raytracing differs from z-buffer oriented methods by being ray centric, as opposed to primitive centric. Instead of drawing primitives to a screen, rays are cast from a virtual eye, or center of projection, through screen pixels (i.e., a view plane) to find intersecting primitives for those pixels. Each pixel has a color set to that of the primitive at the closest point of intersection. While raytracing has existed for quite some time, only recently has research started to make raytracing algorithms run in realtime. Current applications for raytracing include movie and advertising business for precalculated visualizations.
Interactive and realtime raytracing are closely related areas, but are not quite the same. “Interactive” refers to the ability to compute scenes at realtime speeds, without prior knowledge of future frames (e.g., a user may be able to control scene content directly). “Realtime” refers to the ability to compute scenes at speeds sufficiently high to convey the perception of motion to the human eye and allowing an algorithm with knowledge of future frames (more of a prescripted movie approach to animation).
A major limitation on the application of raytracing is the significant computational requirements incurred to render images. A number of proposals have been made to increase the efficiency of raytracing to expand its use in computer graphics. A number of algorithms and architectures for image generation are described by Szirmay-Kalos, László, Theory of Three Dimensional Computer Graphics, Chp. 2, pp. 25-52. In particular, Szirmay-Kalos describes a Digital Differential Analyzer (DDA) line generator used to generate pixel data by applying an incremental concept to scan-line conversion. For a linear function, a line can be drawn using the DDA that eliminates multiplication, non-integer addition, and round operations. The slope of a line is calculated once and is then used to incrementally determine or generate the line.
Fujimoto, A., Tanaka, T., and Iwata, K., “ARTS: Accelerated Ray-Tracing System”, IEEE CG&A, April 1986, pp. 16-26 describe a three-dimensional digital differential analyzer (3DDDA) that seeks to address issues of speed and aliasing in ray-tracing. The 3DDDA is a 3D line generator for traversing a data structure describing a 3-D environment to identify the intersections between rays and objects in the image to be generated. The 3DDDA identifies cells pierced by a ray or straight line and generates the coordinates of the cells. One implementation of a 3DDDA is to use two DDAs synchronized to work in mutually perpendicular planes that intersect along a driving axis DA (i.e., a coordinate axis). In each plane, the respective DDA follows the projection of the 3-D line onto that plane. The coordinate corresponding to the driving axis DA of each DDA is unconditionally incremented by one unit, where the DA is determined by the slope of the line. A control term (or error term) for each DDA measured perpendicular to the DA is updated; this is done by subtracting from the control term the slope value and determining if it satisfies a stipulated condition. Both control terms are measured against the same DDA. If the test fails, a unit increment or decrement of the coordinate perpendicular to the DA is performed for the DDA. The control term is corrected by adding the value corresponding to one pixel whenever underflow occurs.
Setup of a 3DDDA is a significant limitation of the 3DDDA. In particular, the setup involves the following parameters:DX=C/x-delta,DY=C/y-delta, andDZ=C/z-delta,where C is a constant value (e.g., 1 if floating point) and x-delta, y-delta and z-delta components are the absolute coordinates of the vector to be traced through a grid (e.g., for a vector (−1, 23, 4) the x-delta is abs(−1)=1 and y-delta is (abs(23)=23). Disadvantageously, a division is incurred per ray cast. That is, three divisions are incurred for the 3D case. Divisions are computationally costly.
Thus, a need clearly exists for an improved method of ray-tracing using a multi-dimensional DDA that reduces computation time.